package mo.tags.backtrack;

import java.util.Arrays;

public class L698 {

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % k != 0) {
            return false;
        }
        int target = sum / k;
        int[] bucket = new int[k];
        Arrays.sort(nums);
        int i = 0, j = nums.length-1;
        while (i < j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            i++;
            j--;
        }
        return backtrack(nums, 0, bucket, k, target);
    }

    private boolean backtrack(int[] nums, int idx, int[] bucket, int k, int target) {
        if (idx == nums.length) {
            return true;
        }
        for (int i = 0; i < k; i++) {
            if (i > 0 && bucket[i] == bucket[i-1]) {
                continue;
            }
            if (bucket[i] + nums[idx] > target) {
                continue;
            }
            bucket[i] += nums[idx];
            if (backtrack(nums, idx+1, bucket, k, target)) {
                return true;
            }
            bucket[i] -= nums[idx];
        }
        return false;
    }

    public static void main(String[] args) {
        L698 test = new L698();
        System.out.println(test.canPartitionKSubsets(new int[]{1,1,1,1,2,2,2,2}, 2));
    }

}
